package two.chapter_1.c1_5;

public abstract class UF {

    protected int ids[];
    /**
     * 连通分量的数量
     */
    protected int count;

    public UF(int N){
        count=N;
        ids=new int[N];
        for (int i=0;i<N;i++){
            ids[i]=i;
        }
    }

    /**
     * 将p所在连通分量和q所在连通分量连通
     *
     * @param p
     * @param q
     */
    public abstract void union(int p, int q);

    /**
     * 返回触点p所在连通分量
     *
     * @param p
     * @return
     */
    public abstract int find(int p);

    /**
     * 测试p，q是否连通
     *
     * @param p
     * @param q
     * @return
     */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 连通分量的数量
     *
     * @return
     */
    public int count() {
        return count;
    }
}
